package com.zhj.leetcode;

public class UnionFind {
    public int[] root;
    public int[] rank;
    public int count;

    public UnionFind(int length){
        root = new int[length];
        rank = new int[length];
        count = length;
        for (int i = 0; i < length; i++) {
            root[i] = i;
            rank[i] = 0;
        }
    }

    /**
     * 找到某个元素的根节点
     * @param x
     * @return
     */
    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    /**
     * 合并两个元素为同一个根节点
     * @param x
     * @param y
     */
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootX] = rootY;
            count--;
        }
    }

    /**
     * 合并两个元素为同一个根节点
     * @param x
     * @param y
     */
    public void QuickUnion(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]){
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }
}
